package core;

public class BinarySearch {

	/**
	 * Find the index of one occurrence of a key in a sorted array
	 * @param a sorted integer array
	 * @param key integer key to search
	 * @return index of the an occurrence of the key
	 */
	public static int search(int[] a, int key){
		if(a.length == 0) return -1;
		
		int low = 0, high = a.length - 1, mid;
		
		while(high >= low){
			mid = low + (high-low) / 2;
			if(a[mid] == key) return mid;
			else if(a[mid] > key) high = mid - 1;
			else low = mid + 1;
		}
		
		return -1;
	}
	
	
	/**
	 * Find the index of the first occurrence of key in a sorted array
	 * @param a sorted integer array
	 * @param key integer key to search
	 * @return index of the first occurrence of key
	 */
	public static int findFirst(int[] a, int key){
		if(a.length == 0) return -1;
		
		int low = 0, high = a.length - 1, mid; 
		
		while(high >= low){
			mid = low + (high-low) / 2;
			if(a[mid] >= key) high = mid - 1;
			else low = mid + 1;
		}

		if(high > a.length - 2) return -1;
		if(a[high+1] == key) return high+1;
		else return -1;
	}
	
	
	/**
	 * Find the index of the last occurrence of key in a sorted array
	 * @param a sorted integer array
	 * @param key integer key to search
	 * @return index of the last occurrence of key
	 */
	public static int findLast(int[] a, int key){
		if(a.length == 0) return -1;
		
		int low = 0, high = a.length - 1, mid; 
		
		while(high >= low){
			mid = low + (high-low) / 2;
			if(a[mid] <= key) low = mid + 1;
			else high = mid - 1;
		}

		if(low < 1) return -1;
		if(a[low-1] == key) return low-1;
		else return -1;
	}
}
